// 位运算
// 位运算最关键的几个操作：
// 1.取最右边的 ‘1’：num &= (-num)
// 2.消除最右边的 ‘1‘：num &= (num - 1)
// 3.异或运算 ^：相同为 0（消消乐），不同为 1，无进位相加
// 4.位图的思想：如果题目中提出要求不适用额外的数据结构，那么大概率是要使用位图了
// 5.检查某一个 bit：(num >> x) & 1 == 1
// 6.设置某一个 bit：num |= (1 << x);

// 例题 4：
// 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。
// 请你找出并返回那个只出现了一次的元素。
// 你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
//
//        示例 1：
//
//        输入：nums = [2,2,3,2]
//        输出：3
//        示例 2：
//
//        输入：nums = [0,1,0,1,0,1,99]
//        输出：99
//
//
//        提示：
//
//        1 <= nums.length <= 3 * 104
//        -231 <= nums[i] <= 231 - 1
//        nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

// 解题思路：
// 本题找只出现一次的数字，如果其余的元素都出现偶数次，直接异或所有元素就找到只出现一次的数字
// 如果其余的元素出现 3 次或者 3 次以上，出现奇数次，那么需要依次确定只出现一次数字的每一位
// 如果有 n 个元素，那么第 i 位就会出现 3 * 0 ~ 3 * n 个 0 或者 1
// 加上出现一次的数字，就是 3 * 0 ~ 3 * n + 1 个 0 或者 1
// 因此这个数字 % 3，就是单独出现一次数字的第 i 位的值

public class SingleNumber {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for(int i = 0; i < 32; i++){
            int bitSum = 0;
            for(int j = 0; j < nums.length; j++) bitSum += ((nums[j] >> i) & 1);
            bitSum %= 3;
            ret |= (bitSum << i);
        }
        return ret;
    }
}
